<?php
/**
 * @title 2719. 统计整数数目 - 模拟
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {
    /**
     * @param String $num1
     * @param String $num2
     * @param Integer $min_sum
     * @param Integer $max_sum
     * @return Integer
     */
    function count($num1, $num2, $min_sum, $max_sum) {
        /**
         * @since 2024-01-16 避免重复遍历
         */
        $this->dp = [];

        /**
         * @since 2024-01-16 [0, num1]中数字和<=$min_sum-1的好整数个数
         * @since 2024-01-16 [0, num1]中数字和<=$max_sum的好整数个数
         * count2-count1 = [0, num1]中数字和在区间[$min_sum, $max_sum]内的好整数个数
         */
        $count1 = $this->FindCount($num1, $min_sum-1);
        $count2 = $this->FindCount($num1, $max_sum);

        /**
         * @since 2024-01-16 [0, num2]中数字和<=$max_sum的好整数个数
         * @since 2024-01-16 [0, num2]中数字和<=$min_sum-1的好整数个数
         * count4-count3 = [0, num2]中数字和在区间[$min_sum, $max_sum]内的好整数个数
         */
        $count3 = $this->FindCount($num2, $min_sum-1);
        $count4 = $this->FindCount($num2, $max_sum);

        /**
         * @since 2024-01-16 [num1, num2]中数字和在区间[$min_sum, $max_sum]内的好整数个数
         */
        $goodCount = ($count4-$count3) - ($count2-$count1);
        while($goodCount<0){
            $goodCount += pow(10, 9)+7;
        }

        /**
         * @since 2024-01-17 num1是不是好整数
         */
        $sum = 0;
        for($i=0; $i<strlen($num1); $i++){
            $sum += $num1[$i];
        }
        if($sum >= $min_sum AND $sum <= $max_sum){
            $goodCount++;
        } else {}

        /*
         * @return Integer
         */
        return $goodCount % (pow(10, 9)+7);
    }

    /**
     * @title 返回[0, $numString]中数字和<=$digitSum的好整数个数
     * @author start2004
     * @since 2024-01-16 Created
     *
     * @param String $numString
     * @param Integer $digitSum
     * @return Integer
     */
    function FindCount($numString, $digitSum){
        // echo "\n\nFindCount(", $numString ,", ", $digitSum ,")\n";
        $key = "{$numString}-{$digitSum}";
        if(isset($this->dp[$key])){
            return $this->dp[$key];
        } else {}

        /**
         * @since 2024-01-16 特殊情况处理
         */
        if($digitSum < 0) {
            return 0;
        } elseif($digitSum == 0) {
            return 1;
        } else {}

        /**
         * @since 2024-01-16 [0, $numString]中数字和<=$digitSum的好整数个数
         */
        $goodCount = 0;

        /**
         * @since 2024-01-16 数字位数
         */
        $numLength = strlen($numString);

        /**
         * @since 2024-01-16 numLength*9 <= $digitSum，所有位最大值都可以是9
         * @since 2024-01-17 ["1", "10000000000000000000000", 1, 200]
         * sum=200
         * - numString(22个9)+1，溢出
         * - 9*22=198, pow(10, 22)，溢出
         */
        // if($numLength*9 <= $digitSum) {
        //     return $this->dp[$key] = min(intval($numString)+1, pow(10, $numLength)) % (pow(10, 9)+7);
        // } else {}

        /**
         * @since 2024-01-16 当前高位数字
         */
        $digit = intval($numString[0]);

        /**
         * @since 2024-01-16 只有1位
         */
        if($numLength == 1){
            $goodCount += min($digit, $digitSum) + 1;
        } else {
            /**
             * @since 2024-01-16 高位从[0, digit-1]中选择
             */
            for($i=0; $i<min($digit, $digitSum); $i++) {
                /**
                 * @since 2024-01-16 当前高位数字为$i时，低位数字和<=$digitSum-$i的好整数个数
                 */
                $goodCount += $this->FindCount(str_repeat("9", $numLength-1), $digitSum - $i);
            }

            /**
             * @since 2024-01-16 i=min(digit, digitSum) 同时 digitSum <= digit
             * @since 2024-01-17 说明i=digitSum，nextDigitSum=0，低位只能全部取0，goodCount+1
             */
            if($digitSum <= $digit){
                $goodCount++;
            } elseif($digitSum > $digit) {
                $goodCount += $this->FindCount(substr($numString, 1), $digitSum - $digit);
            } else {}
        }

        /**
         * @return Integer
         */
        return $this->dp[$key] = $goodCount % (pow(10, 9)+7);
    }
}

/**
 * @url http://127.0.0.1/leetcode/202401/2024.01.16.php
 */
$datas = [
    // ["1", "12", 1, 8], // 11
    ["4179205230", "7748704426", 8, 46], // 883045899
    // ["1", "10000000000000000000000", 1, 200], // 490000
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    if(count($data) <= 20){
        var_dump($data);
    } else {
        var_dump(count($data));
    }

    $obj = new Solution();
    $result = $obj->count(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
